package zhengqc.sort.quick_sort;
import zhengqc.sort.Sort;

import java.util.Random;

public class SingleWayQuickSort<E extends Comparable<E>> extends Sort<E> {
    private Random random;
    public SingleWayQuickSort() {
        this.sortName = "SingleWayQuickSort";
        this.random = new Random();
    }
    @Override
    public void sort(E[] array) {
        sort(array, 0, array.length-1);
    }
    private void sort(E[] array, int left, int right) {
        if (left >= right) return;
        int p = partition(array, left, right);
        sort(array, left, p-1);
        sort(array, p+1, right);
    }
    private int partition(E[] array, int left, int right) {
        // 生成 [left, right] 之间的随机索引
        int p = left + random.nextInt(right-left+1);
        swap(array, left, p);
        // 循环不变量 array[left+1...j] < v, array[j+1...i] >= v
        int j = left;
        for (int i = left+1; i <= right; ++i) {
            if (array[left].compareTo(array[i]) > 0) {
                ++j;
                swap(array, i, j);
            }
        }
        swap(array, left, j);
        return j;
    }
    private static <E> void swap(E[] array, int i, int j) {
        E t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
